This invention relates to a network system having a router using an associative memory and, in particular, to an associative memory having a mask function.
Referring to FIG. 1, a conventional computer network will be described. A user or a subscriber of the network has a connection apparatus, such as a computer terminal, for connection to the network. The connection apparatus (hereinafter referred to as a user's terminal) is assigned with a specific network address in accordance with a predetermined rule when it is connected to the network. Herein, the network address is represented by a numeral of a plurality of digits of, for example, first through fourth digits (a, b, c, d). The predetermined rule defines a hierarchical structure of the network address. For example, the first digit of the numeral represents a zone, such as Asia, America, and Europe. The second digit of the numeral represents a nation in the zone, such as China and Japan, if the zone is Asia. The third digit of the numeral represents a city in the nation, such as Beijing and Shanghai. In the following description, these hierarchical items will be called areas.
Referring to FIG. 1, each area is depicted by a rectangular block. Specifically, the network includes a first area (AREA1), a second area (AREA2), and a third area (AREA3) at a highest hierarchical level. The first area (AREA1) and the second area (AREA2) include a fourth area (AREA4) and a fifth area (AREA5), respectively. The fourth area (AREA4) and the fifth area (AREA5) include a sixth area (AREA6) and a seventh area (AREA7), respectively. A user's terminal (PC) 301-1 exists in the fifth area. The first area has a network address (1, *, *, *) in which a first digit alone is specified as "1". The fourth area subordinate to the first area has a network address (1, 2, *, *) in which first and second digits "1" and "2" are specified. The sixth area subordinate to the fourth area has a network address (1, 2, 2, *) in which first through third digits "1", "2", and "2" are specified. Thus, the user's terminal 301-1 in the sixth area has a specific or unique network address (1, 2, 2, 3). As will be understood from the above, a symbol "*" contained in these addresses represents "don't care".
In order to connect or establish communication between a plurality of user's terminals in the network, each area is provided with a network router (hereinafter simply called a router). As illustrated in the figure, the first through the seventh areas are provided with first through seventh routers 300-1 through 300-7, respectively. Each router is supplied from any user's terminal or any router connected to the router with transfer data and a transfer address annexed thereto. With reference to the transfer address and the relationship of connection of network apparatuses, the router calculates an optimum transfer route and transfers the transfer data via the optimum transfer route thus calculated.
The user's terminals are not directly connected by the use of the communication channels but carry out communication by controlling network connection by the use of communication control functions of the routers. Thus, communication channels as limited resources are saved.
Next referring to FIG. 2, the third router 300-3 will be described by way of example. Other routers have a similar structure.
The third router 300-3 memorizes, as address information or data, the network addresses for the areas except the third area to which the third router 300-3 belongs. Each digit of each network address is represented by a binary number of two bits. Thus, each network address is represented by a bit sequence of eight bits in total. For example, a network address (1, *, *, *) is represented by a bit sequence (01, 00, 00, 00). Since the symbol "*" represents "don't care" for each of second through fourth digits, it is necessary to indicate that the first and the second bits (01) in the bit sequence (01, 00, 00, 00) alone are valid and the remaining bits (00, 00, 00) are invalid. For this purpose, mask information (or mask data) is combined with the address information or data. In the illustrated example, the mask information (or mask data) is given by a bit sequence (00, 11, 11, 11). Herein, "0" and "1" represent a mask invalid state and a mask valid state, respectively. In the third router 300-3, the address information or data and the mask information or data are stored in an associative memory 100 with a mask function, as illustrated in FIG. 2.
Herein, a typical associative memory with a mask function (hereinafter simply called a mask associative memory) will be described. The mask associative memory can store mask information or data for every single word or every plural words of storage data (namely, the address data). As disclosed in Japanese Unexamined Patent Publication (JP-A) No. 1-220293 (220293/1989), the associative memory has a search (or retrieving) function or a mask searching function in addition to write/read functions of writing and reading storage data at a designated memory address in the manner similar to an ordinary memory circuit. The searching function is for searching same storage data exactly coincident with input search or retrieval data to provide a memory address of the same storage data as a search result. The mask searching function is for searching similar storage data partially coincident with the input search data to provide a memory address of the similar storage data as a search result. Herein, a part of the storage data is excluded from comparison by the use of the mask information.
Referring to FIG. 3, the n-bit/m-word associative memory 100 has first through m-th data word lines 102-1 through 102-m and first through m-th mask word lines 103-1 through 103-m both as input signal lines, first through m-th word match lines 104-1 through 104-m as output signal lines, and first through n-th bit lines 101-1 through 101-n as input/output signal lines. The associative memory 100 comprises first through m-th associative memory words 106-1 through 106-m. Each of the first through the m-th associative memory words 106-1 through 106-m is connected to the first through the n-th bit lines 101-1 through 101-n. Each of the associative memory words 106 (suffixes omitted) is connected to a corresponding one of the data word lines 102 (suffixes omitted) and a corresponding one of the mask word lines 103 (suffixes omitted) both as input lines and to a corresponding one of the word match lines 104 (suffixes omitted) as an output line. For example, the first associative memory word 106-1 is connected to the first data word line 102-1 and the first mask word line 103-1 as the input lines and to the first word match line 104-1 as the output line.
Upon carrying out a writing operation, the first through the n-th bit lines 101-1 through 101-n are supplied from an external source with write data to be written into data cells or mask cells in a desired one of the associative memory words 106. Upon carrying out a reading operation, read data are supplied from the data cells to the first through the n-th bit lines 101-1 through 101-n. In order to write or read the data into and from the data cells, a selected one of the first through the m-th data word lines is activated (active or valid state). Then, a corresponding one of the associative memory words 106 is supplied with the write data on the first through the n-th bit lines 101-1 through 101-n. Alternatively, the read data are supplied from the corresponding associative memory word 106 to the first through the n-th bit lines 101-1 through 101-n. For the mask cells, a similar operation is carried out except that the mask word lines 103 are controlled instead of the data word lines 102. In the following description, the data memorized or to be memorized in the data cells will be referred to as storage data while the data memorized or to be memorized in the mask cell will be referred to as mask storage data.
Upon carrying out a searching operation, search data 105 are supplied from an external source to the bit lines 101. During the searching operation, all of the data word lines 102 and the mask word line 103 are inactivated (invalid state). Each of the word match line 104 is activated (valid state) when all bits of the search data 105 delivered to the bit lines 101-1 through 101-n upon the searching operation are coincident with all bits of the storage data stored in a corresponding one of the associative memory words 106. In case of the mask searching operation, the word match line 104 is activated (valid state) when the search data 105 on the bit lines 101 are partially coincident with the storage data with a part of the storage data excluded from comparison by the use of the mask information or data. Otherwise, the word match line 104 is inactivated (invalid state). Herein, a valid state and an invalid state of the word match line 104 are represented by "1" and "0", respectively.
Each of the first through the m-th associative memory words 106-1 through 106-m comprises a plurality of associative memory cells 107, n in number. For example, the first associative memory words 106-1 comprises first through n-th associative memory cells 107-1-1 through 107-1-n. All of the first through the n-th associative memory cells 107 of each associative memory word 106 are connected to a corresponding one of the data word lines 102 and a corresponding one of the mask word lines 103 both as data input lines. For example, the first through the n-th associative memory cells 107-1-1 through 107-1-n of the first associative memory word 106-1 are connected to the first data word line 102-1 and the first mask word line 103-1.
The first through the n-th associative memory cells 107 of each of the associative memory words 106 are connected in one-to-one correspondence to the first through the n-th bit lines 101 as data input/output lines. For example, the first associative memory cell 107-1-1 of the first associative memory word 106-1 is connected to the first bit line 101-1.
All of the first through the n-th associative memory cells 107 of each of the associative memory words 106 are connected to a corresponding one of the word match lines 104 by wired logic connection in the example being illustrated in FIG. 3. For example, the first through the n-th associative memory cells 107-1-1 through 107-1-n of the first associative memory word 106-1 are connected to the first word match line 104-1 by the wired logic connection.
Each of the associative memory cells 107 comprises a data cell 108, a comparator 109, and a mask cell 110. The data cell 108 stores as the storage data the write data on a corresponding one of the bit lines 101 or supplies the storage data stored therein to the corresponding bit line 101 when a corresponding one of the data word lines 102 is in a valid state. When the corresponding data word line 102 is in an invalid state, no operation is performed for the corresponding bit line 101. Irrespective of the state of the corresponding data word line 102, the storage data stored therein are supplied to the comparator 109.
When a corresponding one of the mask word lines 103 is in a valid state, the mask cell 110 stores as the mask information the write data on the corresponding bit line 101 or supplies the mask information stored therein to the corresponding bit line 101. When the corresponding mask word line 103 is in an invalid state, no operation is performed for the corresponding bit line 101. Irrespective of the state of the corresponding mask word line 103, the mask information stored therein is delivered to the comparator 109.
The comparator 109 is supplied with the value on the corresponding bit line 101, the storage data in the data cell 108, and the mask information in the mask cell 110. When the mask information is in a valid state or when the value on the corresponding bit line 101 and the storage data in the data cell 108 are coincident with each other, the word match line 104 is put into an opened state. Otherwise, the comparator 109 puts the word match line 104 into an invalid state "0".
Prior to the start of the searching operation, the word match line 104 is precharged to a high level or pulled up by a resistor (not shown) to be put into a valid state "1". After the searching operation is started, the word match line 104 and the associative memory cell 107 performs the wired logic so that the word match line 104 is put into a valid state "1" when all of the associative memory cells 107 in the same associative memory word 106 produce a coincidence state and that the word match line 104 is put into an invalid state "0" when any one of the associative memory cells 107 produces an incoincidence state. Alternatively, an ordinary logical gate may be used as far as the similar operation is performed.
Next, the operation will be described. When the writing or the reading operation is performed, the operation is quite similar to that of the ordinary memory circuit. In the reading operation, the write data are not supplied to the bit lines 101-1 through 101-n but a valid state is supplied to a desired one of the data word lines 102-1 through 102-m or a desired one of the mask word lines 103-1 through 103-m while an invalid state is supplied to the remaining ones. At this time, if one of the data word lines 102 is put into a valid state, the storage data stored in a corresponding one of the associative memory words 106 are supplied to the bit lines 101-1 through 101-n. If one of the mask word lines 103 is put into a valid state, the mask information stored in a corresponding one of the associative memory words 106 is supplied to the bit lines 101-1 through 101-n.
In the writing operation, the write data are supplied to the bit lines 101-1 through 101-n. A desired one of the data word lines 102-1 through 102-m or a desired one of the mask word lines 103-1 through 103-m is put into a valid state while the remaining ones are put into an invalid state. At this time, the values on the bit lines 101-1 through 101-n are stored as the storage data in the data cells 108 of one of the associative memory words 106 corresponding to the above-mentioned one of the data word lines 102-1 through 102-m which is put into a valid state. Alternatively, the values on the bit lines 101-1 through 101-n are stored as the mask information in the mask cells 110 of one of the associative memory words 106 corresponding to the above-mentioned one of the mask word lines 103-1 through 103-m which is put into a valid state.
Prior to the start of the searching operation, the word match line 104 is precharged to the high level or pulled up by the resistor (not shown) to be put into a valid state "1", as described above.
Upon the searching operation, the search data 105 are supplied to the bit lines 101-1 through 101-n while all of the data word lines 102-1 through 102-m and all of the mask word lines 103-1 through 103-m are supplied with an invalid state. In each of the associate memory cells 107, the comparator 109 compares the value of the corresponding bit line 101 and the storage data stored in the data cell 108. Upon coincidence, the word match line 104 in the same associative memory word 106 is put into the opened state. Upon incoincidence, the word match line 104 is put into the opened state if the mask information stored in the mask cell 110 of the same associative memory cell 107 is in a valid state. Otherwise, the comparator 109 produces an invalid state "0". Thus, as far as the mask information in the mask cell 110 is kept in a valid state, the storage data stored in the data cell 108 can be excluded from the comparison in the searching operation. The word match line 104 in each associative memory word 106 is put into a valid state when all of the first through the n-th comparators 109 therein render the word match line 104 in the opened state. The word match line 104 is put into an invalid state "0" when at least one of the comparators 109 produces an invalid state. Therefore, if the storage data stored in one of the associative memory words 106 are coincident with the bit lines 101 except those bits excluded by the mask information, the word match line 104 produces a valid state "1". If at least one bit is incoincident, the word match line 104 produces an invalid state "0". It will therefore be understood that, after completion of the searching operation, the same or the similar storage data completely or partially coincident with the search data 105 are stored in one of the associative memory words 106-1 through 106-m which corresponds to a valid-state one of the word match lines 104-1 through 104-m.
The output signals of the word match lines 104-1 through 104-m can directly be used or may be encoded by an encoder to produce address signals for write and read operations in a different memory device. If a valid state is produced from a plurality of ones of the word match lines 104-1 through 104-m greater in number than the address signals to be produced, it is necessary to select ones of the word match lines 104-1 through 104-m for use in generation of the address signals by means of a priority encoder. In order to determine the priority, use is typically made of an ascending or a descending order of the addresses.
Next referring to FIG. 4, the associative memory cell 107 will be described. Two bit lines 101a and 101b correspond to each bit line 101 illustrated in FIG. 3. In FIG. 3, these bit lines 101a and 101b are collectively represented by each single bit line 101-i. Through the two bit lines 101a and 101b, writing and reading of the data into and from the memory cell and the input of the search data 105 are carried out. Upon writing the data or the input of the search data 105, the bit line 101b is supplied with an inverted value of a value on the bit line 101a. The data cell 108 is a typical SRAM (Static Random Access Memory) comprising inverted logical gates (G1 and G2) 201 and 202 with one's input and output terminals connected to the other's output and input terminals, respectively, a MOS (Metal Oxide Semiconductor) transistor (T1) 203 connecting the output terminal of the inverted logical gate (G2) 202 to the bit line 101a and rendered conductive when the data word line 102 has a high level, and a MOS transistor (T2) 204 connecting the output terminal of the inverted logical gate (G1) 201 to the bit line 101b and rendered conductive when the data word line 102 has the high level.
The mask cell 110 is also a typical SRAM comprising inverted logical gates (G3 and G4) 209 and 210 with one's input and output terminals connected to the other's output and input terminals, respectively, a MOS transistor (T7) 211 connecting the output terminal of the inverted logical gate (G4) 210 to the bit line 101a rendered conductive when the mask word line 103 has a high level, and a MOS transistor (T8) 212 connecting the output terminal of the inverted logical gate (G3) 209 to the bit line 101b and rendered conductive when the mask word line 103 has the high level.
The comparator 109 comprises a MOS transistor (T3) 205, a MOS transistor (T4) 206, a MOS transistor (T5) 207, and a MOS transistor (T6) 208. The MOS transistor (T3) 205 and the MOS transistor (T4) 206 are inserted between the bit lines 101a and 101b in cascade. The MOS transistor (T3) 205 is rendered conductive when the inverted logical gate (G1) 201 in the data cell 108 produces an output of a high level. The MOS transistor (T4) 206 is rendered conductive when the inverted logical gate (G2) 202 in the data cell 108 produces an output of a high level. The MOS transistor (T5) 207 and the MOS transistor (T6) 208 are connected between a low potential and the word match line 104 in cascade. The MOS transistor (T5) 207 is rendered conductive when a junction or node of the MOS transistor (T3) 205 and the MOS transistor (T4) 206 has a potential of a high level. The MOS transistor (T6) 208 is rendered conductive when the inverted logical gate (G3) 209 in the mask cell 110 produces an output of a high level. When both the bit line 101a and the inverted logical gate (G1) 201 produce outputs of a high level or when both the bit line 101b and the inverted logical gate (G2) 202 produce outputs of a high level, the junction of the MOS transistor (T3) 205 and the MOS transistor (T4) 206 has a high level to render the MOS transistor (T5) 207 conductive.
Therefore, when the storage data stored in the data cell 108 and the search data 105 on the bit lines 101a and 101b are different from each other, the MOS transistor (T5) 207 is rendered conductive. The MOS transistor (T6) 208 is put into an opened state and a conductive state when the mask information stored in the mask cell 110 is "1" and "0", respectively. The word match line 104 is pulled up to a high potential by the resistor (not shown) or precharged to a high potential prior to the start of the searching operation. This provides the wired AND connection such that, when a plurality of the associative memory cells 107 are connected to the word match line 104 through the MOS transistors (T6) 208, the word match line 104 is given a low level if at least one associative memory cell 107 produces an output of a low level.
When both the MOS transistor (T5) 207 and the MOS transistor (T6) 208 are conductive, the associative memory cell 107 supplied an invalid state "0" to the word match line 104. Otherwise, the word match line 104 is put into an opened state. Specifically, when the mask information is "0", the word match line 104 is put into an opened state. When the mask information is "1", the word match line 104 is put into an opened state and supplied with an invalid state "0" when the search data 105 on the bit lines 101a and 101b and the storage data stored in the data cell 108 are coincident with each other and different from each other, respectively.
Now, description will be turned back to the router illustrated in FIG. 2. As described above, the conventional mask associative memory disregards those portions "*" representing "don't care" upon comparison between the search data and the storage data. Therefore, a plurality of word match lines 104 may sometimes be put into a valid state. Under the circumstances, in order to produce the address signal for write and read operations in another memory device by the use of the search result of the associative memory, it is necessary to preferentially select one of the word match lines 104 in a valid state and to produce a destination address for a selected one of the word match lines 104.
For this purpose, the router is provided with a priority encoder 302 as illustrated in FIG. 2. When a plurality of the word match lines 104 are in a valid state, one of those word match lines 104 is selected. Then, an encoding operation is carried out for the selected one of the word match lines 104 to produce an encoded result which is delivered as a memory address signal 303 to a memory 304. It is assumed here that, among the word match lines 104-1 through 104-5 in a valid state, a particular one having a greater address is preferentially selected.
On the other hand, the memory 304 stores router addresses of the routers 300 corresponding to the network addresses each of which comprises the address information and the mask information and each of which is stored in each word of the associative memory 100. In the memory 304, each router address is memorized in a word corresponding to that of the associative memory 100 where a corresponding network address is memorized. For example, the network address (1, *, *, *) is stored in the word 1 of the associative memory 100 while the router address of the router 300-1 (FIG. 1) corresponding thereto is stored in the word 1 of the memory 304. Similarly, the address of the router 300-2 and the address of the router 300-6 are stored in the word 2 and word 3 of the memory 304, respectively. Supplied with the memory address signal 303 as a read address, the memory 304 produces a memory data signal 305 containing storage data designated by the memory address signal 303.
Although not illustrated in the figure, each router has a CPU for controlling the above-mentioned operation of the router.
In FIGS. 1 and 2, description will be made about a connecting operation in the conventional network controlled by the routers. It is assumed here that the transfer data supplied to the router 300-3 have a destination address (2, 2, 1, 1). As a result of search by the associative memory 100, (2, *, *, *) in the word 2 alone is coincident so that the word match line 104-2 alone is put into a valid state. The priority encoder 302 produces "2" as the memory address signal 303. In response to the memory address signal 303, the memory 304 produces as the memory data signal 305 the network address of the router 300-2. Consequently, the router 300-3 transfers the transfer data having the destination address (2, 2, 1, 1) to the router 300-2. The router 300-2 is responsive to the transfer data and performs the operation similar to that mentioned above. Thus, the transfer data are successively transferred from router to router until the user's terminal at the destination address (2, 2, 1, 1) is reached.
When a plurality of the storage data are coincident with the single search data in the searching operation by the above-mentioned associative memory, all of the word match lines corresponding to those coincident storage data are activated. In order to select one of the word match lines, the priority encoder 302 is required as described in the foregoing.
However, even if one of the word match lines is selected by the priority encoder, it is uncertain whether or not the selected one is an optimum one. For example, it is assumed that the transfer data supplied to the router 300-3 has a destination at the user's terminal (PC) 301-1, i.e., a destination address (1, 2, 2, 3). If the search is carried out by the conventional associative memory 100, (1, *, *, *), (1, 2, 2, *) and (1, 2, *, *) in the word 1, the word 3, and the word 4 are coincident so that the word match lines 104-1, 104-3, and 104-4 are put into a valid state. Herein, the priority encoder 302 produces "4" as the memory address signal 303 because the greater address has a higher priority. That is, the word 4 has the greater address than the word 3. Therefore, the memory 304 produces as the memory data signal 305 the network address of the router 300-4. As a result, the router 300-3 transfers the transfer data having the destination address (1, 2, 2, 3) to the router 300-4.
However, as readily understood from FIG. 1, transfer to the router 300-6 rather than to the router 300-4 provides a shorter route to the user's terminal (PC) 301-1 and is therefore optimum. Thus, it is optimum to select a particular router with the least number of valid bits of the mask information. In case where the conventional associative memory 100 is used in calculating the transfer network address from router to router, selection of one of the routers 300-1, 300-4, and 300-6 as a transfer route is dependent upon the priority which is determined by the order of storage in the associative memory 100 in this example. Thus, it is not assured that the optimum transfer route is selected.
Taking the above into consideration, the CPU contained in the conventional router is loaded with a program for calculating an optimum transfer address. Under control of the program, the optimum address is calculated on the software. It is noted here that the router connected to the internet must deal with network connection information in an amount of more than several tens of thousands of words. Therefore, calculation of the transfer network address by the software requires more than several hundreds of clocks. This is a main factor of occurrence of a large delay in data transfer by the internet.
In the meanwhile, registration and cancellation of users or subscribers of the network are very frequent. The update of the network addresses following the registration and the cancellation of the users must be reflected in the associative memory of the router. For this purpose, the routers communicate with one another at a predetermined time instant to exchange the address information of the users so that the associative memory is automatically updated with the latest network addresses. The above-mentioned exchange of the address information is performed sorting the order of storage of the words in the associative memory in order to achieve the shortest communication routes among the users. However, such sorting takes a long time because the users increase in number from year to year. Therefore, the network inevitably becomes uncommunicable for several tens of seconds.
Furthermore, the router requires the priority encoder which is increased in size in correspondence to the priority function.